package leetcode;

/**
 * Created by lyk on 2017/4/17.
 * Package name: leetcode
 * Porject name: untitled1
 */
public class MaximumGap {
    public static void main(String[] args) {
        MaximumGap mg = new MaximumGap();
        int[] nums = new int[]{110,222,213,456,653,952,233,893,386,217,819,265,456};
        System.out.println(mg.maximumGap(nums));
    }
    public int maximumGap(int[] num) {
        if(num == null || num.length < 2){
            return 0;
        }

        int max = num[0];
        int min = num[0];
        for(int i=1; i<num.length; i++){
            max = Math.max(max, num[i]);
            min = Math.min(min, num[i]);
        }

        // initialize an array of buckets
        Bucket[] buckets = new Bucket[num.length+1]; //project to (0 - n)
        for(int i=0; i<buckets.length; i++){
            buckets[i] = new Bucket();
        }

        double interval = (double) num.length / (max - min);
        //distribute every number to a bucket array
        for(int i=0; i<num.length; i++){
            int index = (int) ((num[i] - min) * interval);

            if(buckets[index].low == -1){
                buckets[index].low = num[i];
                buckets[index].high = num[i];
            }else{
                buckets[index].low = Math.min(buckets[index].low, num[i]);
                buckets[index].high = Math.max(buckets[index].high, num[i]);
            }
        }

        //scan buckets to find maximum gap
        int result = buckets[0].high - buckets[0].low;
        int prev = buckets[0].high;
        for(int i=1; i<buckets.length; i++){
            if(buckets[i].low != -1){
                result = Math.max(result, buckets[i].low-prev);
                result = Math.max(result, buckets[i].high - buckets[i].low);
                prev = buckets[i].high;
            }

        }

        return result;
    }
}
class Bucket{
    int low;
    int high;
    public Bucket(){
        low = -1;
        high = -1;
    }
}
